/*
题目: 最小化数组中的最大值
给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。

每一步操作中，你需要：

    选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
    将 nums[i] 减 1 。
    将 nums[i - 1] 加 1 。

你可以对数组执行 任意 次上述操作，请你返回可以得到的 nums 数组中 最大值 最小 为多少。
https://leetcode.cn/problems/minimize-maximum-of-array/description/
 */
public class MinimizeArrayValue {
    public int minimizeArrayValue(int[] nums) {
        // 二分答案
        // 猜一个答案
        int left = 0, right = Arrays.stream(nums).max().getAsInt();
        while (left <= right) {
            // 猜测的答案
            int gus = left + ((right - left) >> 1);
            // 然后检查这个答案, 并且进行搜索范围的缩小
            long[] cur = new long[nums.length];
            for (int i = 0; i < nums.length; i ++)
                cur[i] = (long) nums[i];
            for (int i = nums.length - 1; i > 0; i --) {
                if (cur[i] > gus) {
                    cur[i - 1] += cur[i] - gus;
                }
            }

            if (cur[0] > gus) { // 最终将反映到 0 这个位置
                // gus 太小了
                left = gus + 1;
            } else {
                // 否则 小于 gus, gus 太大了
                right = gus - 1;
            }
        }
        return right + 1;
    }
}
